
# --------------------------------------------------------------------------------
## 二分归并排序
# 引入同目录下的Binary-merge-sort.py和generator.py，分别是排序算法和随即数生成器
import generator
import alg as Sort
import time
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation


def merge_generate_test():
    """
    生成数据测试
    生成一组随机数据 - 生成int、float或str类型，查看生成是否正确
    """
    data_int = generator.generate_data("int", 10, 1, 10)
    data_float = generator.generate_data("float", 10, 3, 12)
    data_str = generator.generate_data("str", 10)
    print("data_int:", data_int)
    print("data_float:", data_float)
    print("data_str:", data_str)


#
def merge_test1():
    """
    测试1 直接生成少量随机数，并进行测试
    """
    arr = generator.generate_data("int", 10)
    print("Original array - int:", arr)
    print("Ascending sort - int:", Sort.binary_merge_sort(arr))  # 升序排列
    print(
        "Descending sort - int:", Sort.binary_merge_sort(arr, False)
    )  # 降序排列
    arr = generator.generate_data("float", 10, 3, 15, 1)
    print("Original array - float:", arr)
    print("Ascending sort - float:", Sort.binary_merge_sort(arr))  # 升序排列
    print(
        "Descending sort - float:", Sort.binary_merge_sort(arr, False)
    )  # 降序排列
    arr = generator.generate_data("str", 20)
    print("Original array - str:", arr)
    print("Ascending sort - str:", Sort.binary_merge_sort(arr))  # 升序排列
    print(
        "Descending sort - str:", Sort.binary_merge_sort(arr, False)
    )  # 降序排列


def merge_test2():
    """
    测试2 生成大量随机数，并保存到文件，再读取文件进行测试
    """
    # int
    generator.generate_and_save_data(
        "int", 1000, "./data/merge_test2_int.txt", 0, 9
    )  # 生成1000个0-9的整数
    arr = generator.read_data("./data/merge_test2_int.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.binary_merge_sort(arr), "./data/merge_test2_int_sorted.txt"
    )
    generator.save_data(
        Sort.binary_merge_sort(arr, False),
        "./data/merge_test2_int_sorted_desc.txt",
    )
    # float
    generator.generate_and_save_data(
        "float", 1000, "./data/merge_test2_float.txt", 0, 20, 1
    )
    arr = generator.read_data("./data/merge_test2_float.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.binary_merge_sort(arr), "./data/merge_test2_float_sorted.txt"
    )
    generator.save_data(
        Sort.binary_merge_sort(arr, False),
        "./data/merge_test2_float_sorted_desc.txt",
    )
    # str
    generator.generate_and_save_data("str", 1000, "./data/merge_test2_str.txt")
    arr = generator.read_data("./data/merge_test2_str.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.binary_merge_sort(arr), "./data/merge_test2_str_sorted.txt"
    )
    generator.save_data(
        Sort.binary_merge_sort(arr, False),
        "./data/merge_test2_str_sorted_desc.txt",
    )


def merge_test3():
    """
    测试3 鲁棒性测试
    测试通过时,会输出8个passed
    """
    # case1：输入参数arr不是列表
    try:
        Sort.binary_merge_sort("string")
    except ValueError as e:
        print("Test case 1 passed.")
    # case2：输入参数arr为空列表
    try:
        Sort.binary_merge_sort([])
    except ValueError as e:
        print("Test case 2 passed.")
    # case3：输入参数arr中有不可比较的元素
    try:
        Sort.binary_merge_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 3 passed.")
    # case4：输入参数arr中有int和str类型的元素
    try:
        Sort.binary_merge_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 4 passed.")
    # case5：输入参数arr中有int和float类型的元素
    try:
        Sort.binary_merge_sort([1, 2.0, 3])
    except ValueError as e:
        print("Test case 5 passed.")
    # case6：输入参数arr中有float和str类型的元素
    try:
        Sort.binary_merge_sort([1.0, 2.0, "string"])
    except ValueError as e:
        print("Test case 6 passed.")
    # case7：输入参数arr中有int和float和str类型的元素
    try:
        Sort.binary_merge_sort([1, 2.0, "string"])
    except ValueError as e:
        print("Test case 7 passed.")
    # case8：输入参数ascending不是bool类型
    try:
        Sort.binary_merge_sort([1, 2, 3], "string")
    except ValueError as e:
        print("Test case 8 passed.")


def merge_test4():
    """
    测试4 算法性能测试
    生成不同长度的数据并测试排序时间
    以图片显示
    """
    data_len = [
        10,
        100,
        1000,
        3000,
        5000,
        10000,
        20000,
        30000,
        50000,
    ]  # 数据长度
    time_cost = []
    # 生成不同长度的数据并测试排序时间
    for length in data_len:
        data = generator.generate_data("int", length, 0, 100)
        start = time.time()  # 计时开始
        Sort.binary_merge_sort(data)
        end = time.time()  # 计时结束
        time_cost.append(end - start)
    # 绘制图表
    plt.plot(data_len, time_cost, marker="o")
    plt.xlabel("Length of data")
    plt.ylabel("Time cost (s)")
    plt.title("Performance of binary merge sort")
    # 保存图片
    plt.savefig("./image/merge_test4.png")
    plt.show()

    # 二分归并的算法时间复杂度为O(nlogn)
    # 从图中可以看出，随着数据量的增加，排序时间也在增加，但是增加的速度比较慢，符合O(nlogn)的时间复杂度
    # o(nlogn)的时间复杂度是属于多项式级别的


# 测试5 算法可视化 Demo 要先修改一下二分归并排序的代码，因为要返回生成器，记录每一步的操作
# 然后用matplotlib的FuncAnimation来实现类似动画的效果 但是效果不好
def merge_sort(arr, l, r):
    if r - l > 1:
        mid = l + (r - l) // 2
        yield from merge_sort(arr, l, mid)
        yield from merge_sort(arr, mid, r)
        yield from merge(arr, l, mid, r)
        yield arr


def merge(arr, l, mid, r):
    merged = []
    i = l
    j = mid
    while i < mid and j < r:
        if arr[i] < arr[j]:
            merged.append(arr[i])
            i += 1
        else:
            merged.append(arr[j])
            j += 1
    while i < mid:
        merged.append(arr[i])
        i += 1
    while j < r:
        merged.append(arr[j])
        j += 1
    for i, val in enumerate(merged):
        arr[l + i] = val
        yield arr


def visualize(arr):
    fig, ax = plt.subplots()
    bars = ax.bar(range(len(arr)), arr, align="edge")
    ax.set_xlim(0, len(arr))
    ax.set_ylim(0, int(1.07 * max(arr)))
    text = ax.text(0.02, 0.95, "", transform=ax.transAxes)
    iteration = [0]

    def update(arr, rects, iteration):
        for rect, val in zip(rects, arr):
            rect.set_height(val)
        iteration[0] += 1
        text.set_text(f"# of operations: {iteration[0]}")

    anim = FuncAnimation(
        fig,
        func=update,
        fargs=(bars, iteration),
        frames=merge_sort(arr, 0, len(arr)),
        repeat=False,
        blit=False,
        interval=1000,
        save_count=90000,
    )
    plt.show()
# --------------------------------------------------------------------------------

## 插入排序
# --------------------------------------------------------------------------------
def insertion_test():
    arr = generator.generate_data("int", 10)
    print("Original array - int:", arr)
    print("Ascending sort - int:", Sort.insertion_sort(arr))  # 升序排列
    print(
        "Descending sort - int:", Sort.insertion_sort(arr, False)
    )  # 降序排列
    arr = generator.generate_data("float", 10, 3, 15, 1)
    print("Original array - float:", arr)
    print("Ascending sort - float:", Sort.insertion_sort(arr))  # 升序排列
    print(
        "Descending sort - float:", Sort.insertion_sort(arr, False)
    )  # 降序排列
    arr = generator.generate_data("str", 20)
    print("Original array - str:", arr)
    print("Ascending sort - str:", Sort.insertion_sort(arr))  # 升序排列
    print(
        "Descending sort - str:", Sort.insertion_sort(arr, False)
    )  # 降序排列

# --------------------------------------------------------------------------------
# --------------------------------------------------------------------------------
## 冒泡排序
def bubble_generate_test():
    """
    生成数据测试
    生成一组随机数据 - 生成int、float或str类型，查看生成是否正确
    """
    data_int = generator.generate_data("int", 10, 1, 10)
    data_float = generator.generate_data("float", 10, 3, 12)
    data_str = generator.generate_data("str", 10)
    print("data_int:", data_int)
    print("data_float:", data_float)
    print("data_str:", data_str)

def bubble_test1():
    """
    测试1 直接生成少量随机数，并进行测试
    """
    arr = generator.generate_data("int", 10)
    print("Original array - int:", arr)
    print("Ascending sort - int:", Sort.bubble_sort(arr))  

    arr = generator.generate_data("float", 10, 3, 15, 1)
    print("Original array - float:", arr)
    print("Ascending sort - float:", Sort.bubble_sort(arr))  

    arr = generator.generate_data("str", 20)
    print("Original array - str:", arr)
    print("Ascending sort - str:", Sort.bubble_sort(arr))  


def bubble_test2():
    """
    测试2 生成大量随机数，并保存到文件，再读取文件进行测试
    """
    # int
    generator.generate_and_save_data(
        "int", 1000, "./data/bubble_test2_int.txt", 0, 9
    )  # 生成1000个0-9的整数
    arr = generator.read_data("./data/bubble_test2_int.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.bubble_sort(arr), "./data/bubble_test2_int.txt"
    )
    # float
    generator.generate_and_save_data(
        "float", 1000, "./data/bubble_test2_float.txt", 0, 20, 1
    )
    arr = generator.read_data("./data/bubble_test2_float.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.bubble_sort(arr), "./data/bubble_test2_float.txt"
    )
    # str
    generator.generate_and_save_data("str", 1000, "./data/bubble_test2_str.txt")
    arr = generator.read_data("./data/bubble_test2_str.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.bubble_sort(arr), "./data/bubble_test2_str.txt"
    )

def bubble_test3():
    """
    测试3 鲁棒性测试
    测试通过时,会输出8个passed
    """
    # case1：输入参数data不是列表
    try:
        Sort.bubble_sort("string")
    except ValueError as e:
        print("Test case 1 passed.")
    # case2：输入参data为空列表
    try:
        Sort.bubble_sort([])
    except ValueError as e:
        print("Test case 2 passed.")
    # case3：输入参数data中有不可比较的元素
    try:
        Sort.bubble_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 3 passed.")
    # case4：输入参数data中有int和str类型的元素
    try:
        Sort.bubble_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 4 passed.")
    # case5：输入参数data中有int和float类型的元素
    try:
        Sort.bubble_sort([1, 2.0, 3])
    except ValueError as e:
        print("Test case 5 passed.")
    # case6：输入参数data中有float和str类型的元素
    try:
        Sort.bubble_sort([1.0, 2.0, "string"])
    except ValueError as e:
        print("Test case 6 passed.")
    # case7：输入参数data中有int和float和str类型的元素
    try:
        Sort.bubble_sort([1, 2.0, "string"])
    except ValueError as e:
        print("Test case 7 passed.")
    # case8：输入参数ascending不是bool类型
    try:
        Sort.bubble_sort([1, 2, 3], "string")
    except ValueError as e:
        print("Test case 8 passed.")
def bubble_test4():
    """
    测试4 算法性能测试
    生成不同长度的数据并测试排序时间
    以图片显示
    """
    data_len = [
        20,
        200,
        2000,
        4000,
        8000,
        15000,
        30000,
    ]  # 数据长度
    time_cost = []
    # 生成不同长度的数据并测试排序时间
    for length in data_len:
        data = generator.generate_data("int", length, 0, 100)
        start_time = time.time()  # 计时开始
        Sort.bubble_sort(data)
        end_time = time.time()  # 计时结束
        time_cost.append(end_time - start_time)
        print("Runtime:", end_time - start_time, "seconds")  # 打印代码运行时间
    # 绘制图表
    plt.plot(data_len, time_cost, marker="o")
    plt.xlabel("Length of data")
    plt.ylabel("Time cost (s)")
    plt.title("Performance of binary bubble sort")
    # 保存图片
    plt.savefig("./image/heap_test4.png")
    plt.show()

# 经过优化后的冒泡排序在最好情况下的时间复杂度为O(n)，这是通过设置一个标志位来记录每一次遍历时是否进行过元素交换，
# 如果一次遍历中没有进行过元素交换，则说明数组已经有序，可以提前终止排序过程。这种情况下，只需要进行一次遍历就可以完成排序

# --------------------------------------------------------------------------------
# --------------------------------------------------------------------------------
## 快速排序
def quick_test():
   arr = generator.generate_data("int", 100)
   print("Original array - int:", arr)
   print("sort - int:", Sort.QuickSort(arr, start = 0, end = len(arr) - 1))  # 排列
   print(arr)

# --------------------------------------------------------------------------------

# --------------------------------------------------------------------------------
## 堆排序
def heap_generate_test():
    """
    生成数据测试
    生成一组随机数据 - 生成int、float或str类型，查看生成是否正确
    """
    data_int = generator.generate_data("int", 10, 1, 10)
    data_float = generator.generate_data("float", 10, 3, 12)
    data_str = generator.generate_data("str", 10)
    print("data_int:", data_int)
    print("data_float:", data_float)
    print("data_str:", data_str)

def heap_test1():
    """
    测试1 直接生成少量随机数，并进行测试
    """
    arr = generator.generate_data("int", 10)
    print("Original array - int:", arr)
    print("Ascending sort - int:", Sort.heap_sort(arr))  
    print(Sort.heap_sort([1,2,5,4,3]))
    arr = generator.generate_data("float", 10, 3, 15, 1)
    print("Original array - float:", arr)
    print("Ascending sort - float:", Sort.heap_sort(arr))  

    arr = generator.generate_data("str", 20)
    print("Original array - str:", arr)
    print("Ascending sort - str:", Sort.heap_sort(arr))  

def heap_test2():
    """
    测试2 生成大量随机数，并保存到文件，再读取文件进行测试
    """
    # int
    generator.generate_and_save_data(
        "int", 1000, "./data/heap_test2_int.txt", 0, 9
    )  # 生成1000个0-9的整数
    arr = generator.read_data("./data/heap_test2_int.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.heap_sort(arr), "./data/heap_test2_int.txt"
    )
    generator.save_data(
        Sort.heap_sort(arr, False),
        "./data/heap_test2_int.txt",
    )
    # float
    generator.generate_and_save_data(
        "float", 1000, "./data/heap_test2_int.txt", 0, 20, 1
    )
    arr = generator.read_data("./data/heap_test2_int.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.heap_sort(arr), "./data/heap_test2_int.txt"
    )
    generator.save_data(
        Sort.heap_sort(arr, False),
        "./data/heap_test2_int.txt",
    )
    # str
    generator.generate_and_save_data("str", 1000, "./data/heap_test2_int.txt")
    arr = generator.read_data("./data/heap_test2_int.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.heap_sort(arr), "./data/heap_test2_int.txt"
    )
    generator.save_data(
        Sort.heap_sort(arr, False),
        "./data/heap_test2_int.txt",
    )

def heap_test3():
    """
    测试3 鲁棒性测试
    测试通过时,会输出8个passed
    """
    # case1：输入参数data不是列表
    try:
        Sort.heap_sort("string")
    except ValueError as e:
        print("Test case 1 passed.")
    # case2：输入参data为空列表
    try:
        Sort.heap_sort([])
    except ValueError as e:
        print("Test case 2 passed.")
    # case3：输入参数data中有不可比较的元素
    try:
        Sort.heap_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 3 passed.")
    # case4：输入参数data中有int和str类型的元素
    try:
        Sort.heap_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 4 passed.")
    # case5：输入参数data中有int和float类型的元素
    try:
        Sort.heap_sort([1, 2.0, 3])
    except ValueError as e:
        print("Test case 5 passed.")
    # case6：输入参数data中有float和str类型的元素
    try:
        Sort.heap_sort([1.0, 2.0, "string"])
    except ValueError as e:
        print("Test case 6 passed.")
    # case7：输入参数data中有int和float和str类型的元素
    try:
        Sort.heap_sort([1, 2.0, "string"])
    except ValueError as e:
        print("Test case 7 passed.")
    # case8：输入参数ascending不是bool类型
    try:
        Sort.heap_sort([1, 2, 3], "string")
    except ValueError as e:
        print("Test case 8 passed.")

def heap_test4():
    """
    测试4 算法性能测试
    生成不同长度的数据并测试排序时间
    以图片显示
    """
    data_len = [
        10,
        100,
        1000,
        3000,
        5000,
        10000,
        20000,
        30000,
        50000,
    ]  # 数据长度
    time_cost = []
    # 生成不同长度的数据并测试排序时间
    for length in data_len:
        data = generator.generate_data("int", length, 0, 100)
        start_time = time.time()  # 计时开始
        Sort.heap_sort(data)
        end_time = time.time()  # 计时结束
        print("Runtime:", end_time - start_time, "seconds")  # 打印代码运行时间


    # 堆排序的时间复杂度是O(nlogn)
    # 建堆的时间复杂度是O(n)：建立一个大小为n的堆，实际上需要进行n/2次比较和交换操作，以保证堆的性质得以满足。因此建堆的时间复杂度为O(n)。
    # 堆排序的时间复杂度是O(nlogn)：堆排序实际上包含两个步骤，一个是建堆，另一个是将堆顶元素与最后一个元素交换并进行调整操作。建立好堆后，
    # 每次将堆顶元素与最后一个元素交换后，都需要对剩下的元素重新调整成堆。由于每次调整需要的时间复杂度为logn，而总共需要进行n次这样的操作，
    # 因此堆排序的时间复杂度为O(nlogn)

# --------------------------------------------------------------------------------

# --------------------------------------------------------------------------------
## 希尔排序
def shell_generate_test():
    """
    生成数据测试
    生成一组随机数据 - 生成int、float或str类型，查看生成是否正确
    """
    data_int = generator.generate_data("int", 10, 1, 10)
    data_float = generator.generate_data("float", 10, 3, 12)
    data_str = generator.generate_data("str", 10)
    print("data_int:", data_int)
    print("data_float:", data_float)
    print("data_str:", data_str)


#
def shell_test1():
    """
    测试1 直接生成少量随机数，并进行测试
    """
    arr = generator.generate_data("int", 10)
    print("Original array - int:", arr)
    print("Ascending sort - int:", Sort.shell_sort(arr))  # 升序排列
    print(
        "Descending sort - int:", Sort.shell_sort(arr, False)
    )  # 降序排列
    arr = generator.generate_data("float", 10, 3, 15, 1)
    print("Original array - float:", arr)
    print("Ascending sort - float:", Sort.shell_sort(arr))  # 升序排列
    print(
        "Descending sort - float:", Sort.shell_sort(arr, False)
    )  # 降序排列
    arr = generator.generate_data("str", 20)
    print("Original array - str:", arr)
    print("Ascending sort - str:", Sort.shell_sort(arr))  # 升序排列
    print(
        "Descending sort - str:", Sort.shell_sort(arr, False)
    )  # 降序排列


def shell_test2():
    """
    测试2 生成大量随机数，并保存到文件，再读取文件进行测试
    """
    # int
    generator.generate_and_save_data(
        "int", 1000, "./data/shell_test2_int.txt", 0, 9
    )  # 生成1000个0-9的整数
    arr = generator.read_data("./data/shell_test2_int.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.shell_sort(arr), "./data/shell_test2_int_sorted.txt"
    )
    generator.save_data(
        Sort.shell_sort(arr, False),
        "./data/shell_test2_int_sorted_desc.txt",
    )
    # float
    generator.generate_and_save_data(
        "float", 1000, "./data/shell_test2_float.txt", 0, 20, 1
    )
    arr = generator.read_data("./data/shell_test2_float.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.shell_sort(arr), "./data/shell_test2_float_sorted.txt"
    )
    generator.save_data(
        Sort.shell_sort(arr, False),
        "./data/shell_test2_float_sorted_desc.txt",
    )
    # str
    generator.generate_and_save_data("str", 1000, "./data/shell_test2_str.txt")
    arr = generator.read_data("./data/shell_test2_str.txt")
    # 把排序后的数据保存到文件
    generator.save_data(
        Sort.shell_sort(arr), "./data/shell_test2_str_sorted.txt"
    )
    generator.save_data(
        Sort.shell_sort(arr, False),
        "./data/shell_test2_str_sorted_desc.txt",
    )


def shell_test3():
    """
    测试3 鲁棒性测试
    测试通过时,会输出8个passed
    """
    # case1：输入参数data不是列表
    try:
        Sort.shell_sort("string")
    except ValueError as e:
        print("Test case 1 passed.")
    # case2：输入参data为空列表
    try:
        Sort.shell_sort([])
    except ValueError as e:
        print("Test case 2 passed.")
    # case3：输入参数data中有不可比较的元素
    try:
        Sort.shell_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 3 passed.")
    # case4：输入参数data中有int和str类型的元素
    try:
        Sort.shell_sort([1, 2, "string"])
    except ValueError as e:
        print("Test case 4 passed.")
    # case5：输入参数data中有int和float类型的元素
    try:
        Sort.shell_sort([1, 2.0, 3])
    except ValueError as e:
        print("Test case 5 passed.")
    # case6：输入参数data中有float和str类型的元素
    try:
        Sort.shell_sort([1.0, 2.0, "string"])
    except ValueError as e:
        print("Test case 6 passed.")
    # case7：输入参数data中有int和float和str类型的元素
    try:
        Sort.shell_sort([1, 2.0, "string"])
    except ValueError as e:
        print("Test case 7 passed.")
    # case8：输入参数ascending不是bool类型
    try:
        Sort.shell_sort([1, 2, 3], "string")
    except ValueError as e:
        print("Test case 8 passed.")


def shell_test4():
    """
    测试4 算法性能测试
    生成不同长度的数据并测试排序时间
    以图片显示
    """
    data_len = [
        10,
        100,
        1000,
        3000,
        5000,
        10000,
        20000,
        30000,
        50000,
    ]  # 数据长度
    time_cost = []
    # 生成不同长度的数据并测试排序时间
    for length in data_len:
        data = generator.generate_data("int", length, 0, 100)
        start = time.time()  # 计时开始
        Sort.shell_sort(data)
        end = time.time()  # 计时结束
        time_cost.append(end - start)
    # 绘制图表
    plt.plot(data_len, time_cost, marker="o")
    plt.xlabel("Length of data")
    plt.ylabel("Time cost (s)")
    plt.title("Performance of binary shell sort")
    # 保存图片
    plt.savefig("./image/shell_test4.png")
    plt.show()

    # 希尔排序的算法时间复杂度为O(nlogn)
    # 从图中可以看出，随着数据量的增加，排序时间也在增加，但是增加的速度比较慢，符合O(nlogn)的时间复杂度
    # o(nlogn)的时间复杂度是属于多项式级别的

# --------------------------------------------------------------------------------

if __name__ == "__main__":
    # --------------------------------------------------------------------------------
    ## 二分归并排序

    # merge_generate_test()
    # merge_test1()
    # merge_test2()
    # merge_test3()
    # merge_test4()
    # arr = [54, 6, 29, 3, 51, 83, 7, 10, 45, 99, 87]
    # visualize(arr)

    # --------------------------------------------------------------------------------
    ## 插入排序
    #insertion_test()
    # --------------------------------------------------------------------------------

    # --------------------------------------------------------------------------------
    ## 冒泡排序
    # bubble_generate_test()
    # bubble_test1()
    # bubble_test2()
    # bubble_test3()
    # bubble_test4()
    # --------------------------------------------------------------------------------

    # --------------------------------------------------------------------------------
    ## 快速排序
    # quick_test()
    # --------------------------------------------------------------------------------

    # --------------------------------------------------------------------------------
    ## 堆排序
    # heap_generate_test()
    # heap_test1()
    # heap_test2()
    # heap_test3()
    # heap_test4()
    # --------------------------------------------------------------------------------

    # --------------------------------------------------------------------------------
    ## 希尔排序
    # shell_generate_test()
    # shell_test1()
    # shell_test2()
    # shell_test3()
    # shell_test4()
    # --------------------------------------------------------------------------------

